package class4;

import cn.hutool.bloomfilter.bitMap.BitMap;

/**
 *
 * 位运算操作、位图
 * 用“位数”表示数字
 */
public class Code01_BitMap {
    public static void main(String[] args) {

        BitMap bitMap = new BitMap(50);
        long[] bits = bitMap.getBits();
        biary(0, bits[0]);
        bitMap.getBits();
        bitMap.add(0);
        bitMap.add(1);
        bitMap.add(2);
        bitMap.add(3);
        bitMap.add(4);
        biary(0, bits[0]);


        bitMap.delete(1);
        bitMap.delete(2);
        bitMap.delete(3);
//        bitMap.delete(15);
        biary(0, bits[0]);
        boolean contains = bitMap.contains(1);
        System.out.println("contains = " + contains);

    }

    public static void biary(int index, long num) {
        int start = (index << 6);
        int end = ((index + 1) << 6) - 1;
        System.out.print("数组下标：" + index + " 的范围在[" + start + "," + end + "]之间，值为：[ ");
        for (long i = 63; i >= 0; i--) {
            System.out.print((num & (1L << i)) == 0 ? "0" : "1");
            if ((i & 7) == 0) {
                System.out.print(" ");
            }
        }
        System.out.println("]");
    }

    /**
     * 构造一个位图
     * 原理：用long的位数表示数字
     */
    public static class BitMap {
        /**
         * 当需要表示0~63时，需要数组长度为：1的数组，表示64个数
         * long[] bits = new long[]{0}; 0—63
         * 当需要表示更大的数字时，数组长度为：new long[]{0,...};
         * <p>
         * 用4个long的数组数表示：0~255
         * new long[0,0,0,0] => [0~63, 64-127, 128~191, 192~255]
         * 如果每个数都用long表示，那么需要占用 8 * 256 个空间，而位图仅需要用 8 * 4 个空间
         */
        private long[] bits;

        // 构造一个数组，长度位：(max+64)/64 , >>6为除64
        // 判断最大值，需要多个long数组去存
        public BitMap(int max) {
            bits = new long[(max + 64) >> 6];
        }

        public void add(int num) {
            // 1. num >> 6  => num / 64 作用：确定在哪个数组位上
            // 2. num & 63 等价于 num % 63 作用： 确定在哪个整数位上;这部分相当于计算 num 在其所在的 64 位块内，具体是第几位。
            // 3. 1<<(num & 63)  这是将 1 左移 (num & 63) 位，生成一个掩码，掩码的二进制中只有对应的第 (num & 63) 位是 1，其余位是 0。
            // 4. |= 作用：将原有值num与新值做 “或运算” ，得到最后结果
            bits[num >> 6] |= 1L << (num & 63);
            System.out.println("add值为:" + num + ",存放在数组第 " + (num >> 6) + " 个之中,1向左偏移:" + (num & 63));
        }

        public void delete(int num) {
            System.out.println("移除值为:" + num + ",存放在数组第 " + (num >> 6) + " 个之中,0向左偏移:" + (num & 63));
            // 1.先将 1左移到 &63的位置上,再对其取反:
            // 移动: 00001000
            // 取反: 11110111
            // 2.将值与"取反"的值做 & 操作
            // 3.完成删除操作
            bits[num >> 6] &= ~(1L << (num & 63));
        }

        public boolean contains(int num) {
            // 用bits[index]位上的数,与指定位为1的数进行 & 操作,如果!=0,则数字存在
            // 例如:判断数组中从 0,3,4的数组中,判断2是否存在,
            // 如果存在,结果不为0,不存在,结果==0;
            //  0005 1001 (0,3,4)
            //& 0000 0100 (2)
            return ((bits[num >> 6]) & (1L << (num & 63))) != 0;
        }

        public long[] getBits() {
            return bits;
        }
    }


    /**
     * 右移操作
     */
    private static void rightMove() {
        int num = 64;
        System.out.println(num >> 1); // 除2
        System.out.println(num >> 2); // 除4
        System.out.println(num >> 3); // 除8
        System.out.println(num >> 4); // 除16
        System.out.println(num >> 5); // 除32
        System.out.println(num >> 6); // 除64
    }

}
